package Simple;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

import org.omg.CORBA.PUBLIC_MEMBER;

/**
 * Find the kth nearest point from (0,0)
 * @author YC
 *
 */
public class K_nearest_points {

  public static class Point {

    public double x;

    public double y;

  } 
  public static Point[] closestk( Point  myList[], int k ) {
	  
	  HashMap<Integer, Double> myPoint = new HashMap<Integer,Double>();
	  Comparator myComparator =  new ValueComparator(myPoint);
	  TreeMap<Integer,Double> sortedPoint = new TreeMap<Integer,Double>(myComparator);
	  
	  //first compute the distance for each point and store it 
	  //into a hashmap.
	  for(int i = 0; i != myList.length; ++i) {
		  double distance = myList[i].x*myList[i].x + myList[i].y*myList[i].y;
		  myPoint.put(i, distance);
	  }
	  
	  sortedPoint.putAll(myPoint);
	  ArrayList<Point> kNearest = new ArrayList<Point>();
	  Object[] keySet = sortedPoint.keySet().toArray();
	  for(int i = 0; i != k; ++i){
		  kNearest.add(myList[(Integer)keySet[i]]);
	  }
	  return (Point[]) kNearest.toArray();
	}
  
  public static void main (String[] args){
	}
}

class ValueComparator implements Comparator<Double> {

	    Map<Integer, Double> base;
	    public ValueComparator(Map<Integer, Double> base) {
	        this.base = base;
	    }

		public int compare(Double o1, Double o2) {
			if(base.get(o1) >= base.get(o2)){
				return -1;
			} else {
				return 1;
			}
		}
	}